package leetcode_周赛._2022._202207;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/7/10 18:45
 * 301 场周赛
 */
public class _10 {

    /**
     * 6112. 装满杯子需要的最短总时长
     * 现有一台饮水机，可以制备冷水、温水和热水。每秒钟，可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
     * 给你一个下标从 0 开始、长度为 3 的整数数组 amount ，其中 amount[0]、amount[1] 和 amount[2]
     * 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。
     * 算法：贪心 + 分类讨论
     * 思路：匹配尽量多不同类型的水
     * 将数组从小到大排序, 如果 amount[0] + amount[1] <= amount[2], 表明 amount[2] 可以匹配 amount[0] 和 amount[1]
     * 反之, amount[0] + amount[1] > amount[2], 表示 amount[2] 不可以同时匹配前面两种
     * 这时前面两种可以先自己匹配, 然后再跟第三种匹配. t = amount[0] + amount[1] - amount[2]
     * t 表示前面两种比第三种多出来的数量
     * 如果 t 为偶数, 则前面两种先匹配 (t / 2) 次
     * 如果 t 为奇数, 则前面两种先匹配 ((t + 1) / 2) 次
     */
    public int fillCups(int[] amount) {
        Arrays.sort(amount);
        if (amount[0] + amount[1] <= amount[2]) return amount[2];
        else {
            int t = amount[0] + amount[1] - amount[2];
            return (t + 1) / 2 + amount[2];
        }
    }

    /**
     * 6113. 无限集中的最小数字
     * 算法：模拟
     * 没有通过, 在做的时候没有看条件 1 <= num <= 1000, 因为真的是无穷了
     */
    static class SmallestInfiniteSet {
        TreeSet<Integer> ts;

        public SmallestInfiniteSet() {
            ts = new TreeSet<>();
            /*
            因为题目说 pop 和 add 方法共计 1000 次
            假设 1000 次都调用 pop, 因为 pop 方法中使用的是 ts.first
            防止 ts.first() 连续调用 1000 后返回空, 所以存储 1001
             */
            for (int i = 1; i <= 1001; i++) ts.add(i);
        }

        public int popSmallest() {
            int num = ts.first();
            ts.remove(num);
            return num;
        }

        public void addBack(int num) {
            ts.add(num);
        }
    }

}
